public class J6_3 {
    //递归
    //代码⽰例: 递归求 N 的阶乘
    public static void main(String[] args) {
        int n = 5;
        int ret = factor(n);
        System.out.println("ret = " + ret);
    }
//    public static int factor(int n) {
//        if (n == 1) {
//            return 1;
//        }
//        return n * factor(n - 1); // factor 调⽤函数⾃⾝
//    }
// 执⾏结果 ret = 120
     public static int factor(int n) {
         System.out.println("函数开始, n = " + n);
         if (n == 1) {
         System.out.println("函数结束, n = 1 ret = 1");
         return 1;
         }
         int ret = n * factor(n - 1);
          System.out.println("函数结束, n = " + n + " ret = " + ret);
    return ret;
    }
// 执⾏结果
//    函数开始, n = 5
//    函数开始, n = 4
//    函数开始, n = 3
//    函数开始, n = 2
//    函数开始, n = 1
//    函数结束, n = 1 ret = 1
//    函数结束, n = 2 ret = 2
//    函数结束, n = 3 ret = 6
//    函数结束, n = 4 ret = 24
//    函数结束, n = 5 ret = 120
//    ret = 120

    //代码⽰例1 按顺序打印⼀个数字的每⼀位(例如 1234 打印出 1 2 3 4)
    public static void print(int num) {
        if (num > 9) {
            print(num / 10);
        }
        System.out.println(num % 10);
    }
    //代码⽰例2 递归求 1 + 2 + 3 + ... + 10
    public static int sum1(int num) {
        if (num == 1) {
            return 1;
        }
        return num + sum(num - 1);
    }
    //代码⽰例3 写⼀个递归⽅法，输⼊⼀个⾮负整数，返回组成它的数字之和. 例如，输⼊ 1729, 则应该返回1+7+2+9，它的和是19
    public static int sum(int num) {
        if (num < 10) {
            return num;
        }
        return num % 10 + sum(num / 10);
    }
//    代码⽰例4 求斐波那契数列的第 N 项
    public static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }
    //可以使⽤循环的⽅式来求斐波那契数列问题, 避免出现冗余运算.
    public static int fib2(int n) {
        if(n == 1 || n == 2) {
            return 1;
        }
        int last2 = 1;
        int last1 = 1;
        int cur = 0;
        for (int i = 3; i <= n; i++) {
            cur = last1 + last2;
            last2 = last1;
            last1 = cur;
        }
        return cur;
    }
    //此时程序的执⾏效率⼤ 提⾼了
}
